package com.datastructure.linkedlist;

import java.util.Stack;

public class DoubleLinkedListDemo {

    public static void main(String[] args) {
        // 进行测试
        // 先创建节点
        HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨");
        HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟");
        HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星");
        HeroNode2 hero4 = new HeroNode2(4, "林冲", "豹子头");

        // 创建给链表
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        DoubleLinkedList doubleLinkedList1 = new DoubleLinkedList();
        DoubleLinkedList doubleLinkedList2 = new DoubleLinkedList();
        // 加入
//        doubleLinkedList.add(hero1);
//        doubleLinkedList.add(hero2);
//        doubleLinkedList.add(hero3);
//        doubleLinkedList.add(hero4);
//        doubleLinkedList.addByOrder(hero2);
//        doubleLinkedList.addByOrder(hero4);
//        doubleLinkedList.addByOrder(hero3);
//        doubleLinkedList.addByOrder(hero1);
        doubleLinkedList.addByOrder(hero2);
        doubleLinkedList.addByOrder(hero4);
        doubleLinkedList1.addByOrder(hero3);
        doubleLinkedList1.addByOrder(hero1);
        // 显示一把
//        doubleLinkedList.list();

        // 合并两个链表
        HeroNode2 heroNode = mergeLinkedList(doubleLinkedList.getHead(), doubleLinkedList1.getHead());
        doubleLinkedList2.add(heroNode);
        doubleLinkedList2.list();
        // 测试修改节点的代码
//        HeroNode2 newHeroNode = new HeroNode2(2,"小卢", "玉麒麟~~");
//        doubleLinkedList.update(newHeroNode);
//
//        System.out.println("修改之后的链表情况～～");
//        doubleLinkedList.list();
//
//        // 删除一个节点
//        doubleLinkedList.del(1);
//        System.out.println("删除后的链表情况～～");
//        doubleLinkedList.list();
//
        // 测试一下，求单链表中有效节点的个数
//        System.out.println("有效节点的个数"+getLength(doubleLinkedList.getHead()));

        // 测试一下看看是否得到了倒数第K个节点
//        HeroNode2 res = findLastIndexNode(doubleLinkedList.getHead(), 2);
//        System.out.println("res=" + res);

//        // 测试一下，反转
//        System.out.println("反转");
//        reversetList(doubleLinkedList.getHead());
//        doubleLinkedList.list();
//
//        // 测试，逆序打印
//        System.out.println("测试逆序打印单链表，没有改变链表的结构");
//        reversePrint(doubleLinkedList.getHead());
    }
    // 方法: 获取单链表的节点的个数(如果是带头节点的链表，需求不统计头节点)
    public static int getLength(HeroNode2 head){
        if(head.next == null){ // 空链表
            return 0;
        }
        int length = 0;
        // 定义一个辅助的变量，这里我们没有统计头节点
        HeroNode2 cur = head.next;
        while (cur != null){
            length++;
            cur = cur.next;
        }
        return length;
    }

    // 找到倒数第几个元素
    public static HeroNode2 findLastIndexNode(HeroNode2 head, int index){
        // 判断如果链表为空，返回null
        if(head.next == null){
            return null;//没有找到
        }
        // 第一个遍历得到链表的长度(节点的个数)
        int size = getLength(head);
        // 第二次遍历 size-index 位置，就是我们倒数的第K个节点
        // 先做一个index的校验
        if(index <= 0 || index > size){
            return null;
        }
        // 定义辅助变量，for循环定位到倒数的index
        HeroNode2 cur = head.next; //3 // 3 - 1 = 2
        for(int i = 0; i < size - index; i++){
            cur = cur.next;
        }
        return cur;
    }

    // 将链表反转
    public static void reversetList(HeroNode2 head){
        // 如果当前链表为空，或者只有一个节点，无需反转，直接返回
        if(head.next == null || head.next.next == null){
            return;
        }

        // 定义一个辅助的指针(变量)，帮助我们遍历原来的链表
        HeroNode2 cur = head.next;
        HeroNode2 next = null; // 指向当前节点[cur]的下一个节点
        HeroNode2 reverseHead = new HeroNode2(0, "", "");
        // 遍历原来的链表，没遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端
        // 动脑经
        while (cur != null){
            next = cur.next; // 先暂时保存当前节点的下一个节点，因为后面需要使用
            cur.next = reverseHead.next; // 将cur的下一个节点指向新的链表的最前端,也是进行一个保存
            reverseHead.next = cur;
            cur.pre=reverseHead;
            cur = next; // 让cur后移
        }
        // 将head.next 指向 reverseHead.next,实现单链表的反转
        head.next = reverseHead.next;
    }

    // 可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果
    public static void reversePrint(HeroNode2 head){
        if (head.next == null){
           return;// 空链表，不能打印
        }
        // 创建一个栈，将各个节点压入栈中
        Stack<HeroNode2> stack = new Stack<>();
        HeroNode2 cur = head.next;
        // 将链表的所有节点压入栈
        while (cur != null){
            stack.push(cur);
            cur = cur.next; // cur后移，这样就可以压入下一个节点
        }
        // 将栈中的节点进行打印，pop出栈
        while (stack.size() > 0){
            System.out.println(stack.pop());
        }
    }

    // 将两个链表合并
    public static HeroNode2 mergeLinkedList(HeroNode2 first, HeroNode2 second){
        HeroNode2 initHeroNode = new HeroNode2(0,"","");
        if(first.next ==null || second.next==null){
            //System.out.println("两个链表中的任何一个都不可以空!");
            return initHeroNode;
        }
        HeroNode2 cur = first.next;
        HeroNode2 cur2;
        while (true){
            if (cur==null){
                break;
            }
            cur2=new HeroNode2(cur.no,cur.name,cur.nickname);
            addByOrder(initHeroNode,cur2);
            cur = cur.next;
        }
        HeroNode2 cur1 = second.next;
        while (true){
            if (cur1==null){
                break;
            }
            cur2=new HeroNode2(cur1.no,cur1.name,cur1.nickname);
            addByOrder(initHeroNode,cur2);
            cur1 = cur1.next;
        }
        return initHeroNode;
    }
    public static void addByOrder(HeroNode2 head, HeroNode2 heroNode){
        // 因为头节点不能动，所以我们仍然通过一个辅助指针(变量)来帮助寻找添加的位置
        // 因为单链表，因为我们找的temp是位于添加位置的前一个节点，否则插入不了
        HeroNode2 temp = head;
        boolean flag = false; // flag标志添加的编号是否存在，默认为false
        while (true) {
            if(temp.next == null){ // 说明temp已经在链表的最后
                break;
            }
            if(temp.next.no > heroNode.no){ // 位置找到，就在temp的后面插入
                break;
            } else if (temp.next.no == heroNode.no){ // 说明希望添加的heroNode的编号已然存在
                flag = true; // 说明编号存在
                break;
            }
            temp = temp.next; // 后移，遍历当前链表
        }
        // 判断flag的值
        if(flag){ // 不能添加，说明编号存在
            System.out.printf("准备插入的英雄编号%d已经存在了，不能加入\n", heroNode.no);
        } else {
            // 插入到链表中，temp的后面
            if(temp.next==null){
                temp.next=heroNode;
                heroNode.pre=temp;
            }else {
                heroNode.next = temp.next;
                temp.next.pre=heroNode;
                temp.next=heroNode;
                heroNode.pre=temp;
            }
        }

    }

}

// 定义SingleLinkedList 管理我们的英雄
class DoubleLinkedList {
    // 先初始化一个头节点，头节点不要动，不存放具体的数据
    private HeroNode2 head = new HeroNode2(0,"","");

    // 返回头节点
    public HeroNode2 getHead() {
        return head;
    }

    // 添加节点到单向链表
    // 思路，当不考虑编号顺序时
    // 1.找到当前链表的最后一个节点
    // 2.将最后这个节点的next指向新的节点
    public void add(HeroNode2 heroNode2){

        // 因为head节点不能动，因为我们需要一个辅助遍历temp
        HeroNode2 temp = head;
        // 遍历链表，找到最后
        while (true) {
            // 找到链表的最后
            if(temp.next == null){
                break;
            }
            // 如果没有找到最后，将temp后移
            temp = temp.next;
        }
        // 当退出while循环时，temp就指向了链表的最后
        // 将最后这个节点的next 指向 新的节点
        // 形成一个双向链表
        temp.next = heroNode2;
        heroNode2.pre = temp;
    }

    // 显示链表[遍历]
    public void list(){
        // 判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        // 因为头节点，不能动，因此我们需要一个辅助变量来遍历
        HeroNode2 temp = head.next;
        while(true){
            // 判断是否到链表最后
            if(temp == null){
                break;
            }
            // 输出节点的信息
            System.out.println(temp);
            // 将temp后移，一定小心
            temp = temp.next;
        }
    }

    //修改节点的值，根据no编号来修改，即no编号不能够修改
    // 说明
    // 1.根据newHeroNode的no来修改
    public void update(HeroNode2 newHeroNode2){
        // 判断是否空
        if(head.next == null){
            System.out.println("链表为空～");
            return;
        }
        // 找到需要修改的节点，根据no编号
        // 定义一个辅助变量
        HeroNode2 temp = head.next;
        boolean flag = false; // 表示是否找到该节点
        while (true){
            if(temp == null){
                break; // 已经遍历完链表
            }
            if(temp.no == newHeroNode2.no){
                // 找到
                flag = true;
                break;
            }
            temp = temp.next;
        }
        // 根据flag 判断是否找到要修改的节点
        if(flag){
            temp.name = newHeroNode2.name;
            temp.nickname = newHeroNode2.nickname;
        } else { // 没有找到
            System.out.printf("没有找到编号 %d 的节点，不能修改\n", newHeroNode2.no);
        }
    }

    // 删除节点
    // 思路
    // 1.对于双向链表，我们可以直接找到要删除的这个节点
    // 2.找到后，自我删除即可
    public void del(int no){
        // 判断当前列表是否为空
        if(head.next == null){ // 空链表
            System.out.println("链表为空，无法删除");
            return;
        }
        HeroNode2 temp = head; // 辅助变量(指针)
        boolean flag = false; // 标志是否找到待删除节点的
        while (true){
            if(temp.next == null){ // 已经到链表的最后
                break;
            }
            if (temp.no == no){
                // 找到带删除节点的前一个节点temp
                flag = true;
                break;
            }
            temp = temp.next; // temp后移，遍历
        }
        // 判断flag
        if(flag){ // 找到
            // 可以删除
            // temp.next = temp.next.next; 单向链表的删除方式
            temp.pre.next = temp.next;
//            temp.next.pre = temp.pre;
            // 如果是最后一个节点，就不需要执行下面这句话，否则出现空指针
            if(temp.next != null){
                temp.next.pre = temp.pre;
            }
        } else {
            System.out.printf("要删除的节点%d 节点不存在\n", no);
        }
    }

    // 按顺序添加子节点
    public void addByOrder(HeroNode2 heroNode2){
        // 因为头节点不能动，所以我们仍然通过一个辅助指针(变量)来帮助寻找添加的位置
        // 因为单链表，因为我们找的temp是位于添加位置的前一个节点，否则插入不了
        HeroNode2 temp = head;
        boolean flag = false; // flag标志添加的编号是否存在，默认为false
        while (true) {
            if(temp.next == null){ // 说明temp已经在链表的最后
                break;
            }
            if(temp.next.no > heroNode2.no){ // 位置找到，就在temp的后面插入
                break;
            } else if (temp.next.no == heroNode2.no){ // 说明希望添加的heroNode的编号已然存在
                flag = true; // 说明编号存在
                break;
            }
            temp = temp.next; // 后移，遍历当前链表
        }
        // 判断flag的值
        if(flag){ // 不能添加，说明编号存在
            System.out.printf("准备插入的英雄编号%d已经存在了，不能加入\n", heroNode2.no);
        } else {
            // 插入到链表中，temp的后面
            if(temp.next==null){
                temp.next=heroNode2;
                heroNode2.pre=temp;
            }else {
                heroNode2.next = temp.next;
                temp.next.pre=heroNode2;
                temp.next=heroNode2;
                heroNode2.pre=temp;
            }
        }
    }
}

// 定义HeroNode，每个HeroNode 对象就是一个节点
class HeroNode2 {
    public int no;
    public String name;
    public String nickname;
    public HeroNode2 next; // 指向下一个节点,默认为null
    public HeroNode2 pre;  // 指向下一个节点，默认为null
    // 构造器
    public HeroNode2(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }
    // 为了显示方法，我们重写toString

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}
